/**********************************************************************
**	Authors: Erik Sapir & Lior Zibi

**
** Optimistic Global List implementation: search that element exist 
** and than lock using global lock
**
**
**********************************************************************/
 
#ifndef __OPTIMISTIC_GLOBAL_LIST__H
#define __OPTIMISTIC_GLOBAL_LIST__H


#include "framework/cpp_framework.h"
#include <memory>
#include "set.h"

using namespace CMDR;

template<typename T>
class OptimisticGlobalList : public set<T> {

private:
	//list node
	class Node : public HazardMemory::Object {
	public:
		const T					m_item; // item stored in node
		VolatileType<Node*>	m_next; //next node in list

		Node(const T& item) : m_item(item), m_next(null) { }
		Node(const T& item, Node* const next) : m_item(item), m_next(next) { }

		virtual ~Node() {;}

		virtual bool isValid() { return true; }
		virtual HazardMemory::Object* getNextValid(const int indx) {
			return m_next;
		}
		virtual HazardMemory::Object* getNextValid(const int indx, int& flag) {
			flag = 0; 
			return m_next;
		}
	};

private:

	VolatileType<Node*>	m_head; //first list node
	CMDR::ReentrantLock			m_lock; //Synchronizes access to list
	VolatileType<int>		m_size; // number of element in the list

public:

	OptimisticGlobalList(int numOfThreads) :  m_size(0) {
		printf("\n\tSet Is: Optimistic Global List\n");

		// Add sentinels to start and end
		m_head = new Node(Integer::MIN_VALUE, null);
		Node* tail = new Node(Integer::MAX_VALUE);
		m_head->m_next = tail;
	}

	//desctructor - removes all list elements
	~OptimisticGlobalList() {
		//we assume no one access the object at this point.
		Node* curr = m_head;
		Node* next = null;

		//go ovel all list elements and delete them
		while(null != curr) {
			next = curr->m_next;
			delete curr;
			curr = next;
		}
	}

	bool add(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;
		int returnCode = 2;
		while (true) {
			pred = m_head;
			curr.extractNext(pred, 0);
			while (curr->m_item < item) {	
				pred = curr;
				curr.extractNext(pred, 0);
			}

			//once found - lock the list
			m_lock.lock();
			try {
				//make sure pred and curr still exist and list and that pred.next = curr 
				if (validate(pred,curr)) {
					if (curr->m_item == item) {
						// element already exist in list - nothing to add
						returnCode = 1;
					}
					else {
						// add element to list
						std::auto_ptr<Node> node(new Node(item, curr.getReference()));
						pred->m_next = node.get();

						node.release();
 
						//element added successfully - increment number of elements in list
						m_size++;

						returnCode = 0;
					}
				}
			} catch (const std::exception& ){
				returnCode = 1;
			}
			
			//unlock list
			m_lock.unlock();

			if (returnCode == 0)
				return true;
			else if (returnCode ==1)
				return false;
		}
	}

	bool remove(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;
		int returnCode = 2;

		while (true) {
			pred = m_head;
			curr.extractNext(pred, 0);

			//search for first element equal or larger than element to be removed
			while (curr->m_item < item) {	
				pred = curr;
				curr.extractNext(pred, 0);
			}

			//lock the list
			m_lock.lock();

			try {
				if (validate(pred,curr)) {
					if (curr->m_item == item) {
						// remove element from list
						pred->m_next = curr->m_next;

						//retire node - will be acctually deleted when not used anymore
						curr.retire();

						//element removed successfully - decrement number of elements in list
						m_size--;
						returnCode = 0;
					}
					else {
						// element was not found in list - nothing to remove
						returnCode = 1;
					}
				}
			} catch (const std::exception& ){
				returnCode = 1;
			}
			
			//unlock list
			m_lock.unlock();

			if (returnCode == 0)
				return true;
			else if (returnCode ==1)
				return false;
		}
	}

	bool contains(const T& item, int threadID) {
		HazardMemory::Ptr<Node> pred;
		HazardMemory::Ptr<Node> curr;
		int returnCode = 2;
		while (true) {
			pred = m_head;
			curr.extractNext(pred, 0);

			//search for first element equal or larger than element we are searching
			while (curr->m_item < item) {	
				pred = curr;
				curr.extractNext(pred, 0);
			}

			//lock the list
			m_lock.lock();

			try {
				//make sure pred and curr still exist and list and that pred.next = curr 
				if (validate(pred,curr)) {

					//return true iff element is in the list
					if (curr->m_item == item) {
						returnCode = 0;
					}
					else {
						returnCode = 1;
					}
				}
			} catch (const std::exception& ){
				returnCode = 1;
			}

			//unlock list
			m_lock.unlock();

			if (returnCode == 0)
				return true;
			else if (returnCode ==1)
				return false;
		}
	}

	void clean(int threadID) {
		//lock the list - than remove all elements from list
		m_lock.lock(); 


		//crreate new tail, se head.next = newTails and
		//than delete all old elements
		Node* newTail = new Node(Integer::MAX_VALUE);
		Node* oldFirst = m_head->m_next;
		m_head->m_next = newTail;

		//no elements in the list now
		m_size = 0;

		HazardMemory::Ptr<Node> curr;
		HazardMemory::Ptr<Node> succ;
		curr = oldFirst;

		//remove all elements from list
		do {
			succ.extractNext(curr, 0);

			//retire node - will be acctually deleted when not used anymore
			curr.retire();
			curr = succ;
		} while(null != curr.getReference());

		//unlock list
		m_lock.unlock();
	}
	bool isEmpty(int threadID) {
		return m_size == 0;
	}
	int size(int threadID){
		return m_size;
	}

private:

	/*
	 * Check that prev and curr are still in list and adjacent
	 */
	bool validate(HazardMemory::Ptr<Node>& pred, HazardMemory::Ptr<Node>& curr) {
		HazardMemory::Ptr<Node> entry;
		HazardMemory::Ptr<Node> nextEntry;
		entry = m_head;
		while (entry->m_item<= pred->m_item) {
			if (entry == pred)
				//make sure pred and curr and adjacent
				return pred->m_next == curr.getReference();
			nextEntry.extractNext(entry, 0);
			entry = nextEntry;
		}
		return false;
	}
};

#endif //__OPTIMISTIC_GLOBAL_LIST__H
